package com.czk.sort;

import java.util.Arrays;

/**
 * 基数排序
 * 经典空间换时间的算法，占用内存较大，会有堆溢出的风险
 *
 * @Author:ChenZhangKun
 * @Date: 2020/6/30 19:29
 */
public class RadixSort {
    public static void main(String[] args) {
        int[] array = {53, 3, 542, 748, 14, 214};
        radixSort(array);
    }

    // 基数排序的方法
    public static void radixSort(int[] array) {
        // 拿到最大的数
        int max = array[0];
        for (int i = 0; i < array.length; i++) {
            if (array[i] > max) {
                max = array[i];
            }
        }
        // 得到max的最大位数
        int maxLength = (max + "").length();
        // 第一轮排序，针对元素的个位排序
        // 定义一个二维数组表示十个桶
        // 为了防止放数据的时候数据溢出，每个一维数组定位为array.length,是空间换时间的经典算法
        int[][] bucket = new int[10][array.length];
        // 为了记录每个桶中实际存放了多少个数据，我们定义一个一维数组来记录每个桶中的存放的数量
        int[] bucketElementCount = new int[10];
        // 排序
        for (int n = 1; n <= maxLength; n++) {
            // 每次除以10,100,1000以此类推
            int m = (int) Math.pow(10, n - 1);
            // 第n轮，针对元素的各位进行排序
            for (int i = 0; i < array.length; i++) {
                // 取出每个元素的个位
                int digitOfElement = array[i] / m % 10;
                // 存放在该桶的位置
                bucket[digitOfElement][bucketElementCount[digitOfElement]] = array[i];
                // 存放数目加一
                bucketElementCount[digitOfElement]++;
            }
            int index = 0;
            // 遍历每个桶，并将桶中数据放入原数组
            for (int i = 0; i < bucket.length; i++) {
                // 如果桶中有数据，则让如原数组中
                if (bucketElementCount[i] != 0) {
                    // 有数据
                    for (int j = 0; j < bucketElementCount[i]; j++) {
                        // 取出元素，放入array中
                        // 第i个桶的第j个元素
                        array[index] = bucket[i][j];
                        index++;
                    }
                }
                // 第二轮开始前需要将计数桶清零
                bucketElementCount[i] = 0;
            }

        }
        System.out.println(Arrays.toString(array));
    }
}
